'''
https://leetcode.cn/problems/kth-smallest-element-in-a-bst/?envType=study-plan-v2&envId=top-interview-150
'''

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        cnt = 0
        res = 0
        def f(root):
            if not root: return
            nonlocal cnt, res
            f(root.left)
            cnt += 1
            if cnt == k: res = root.val
            f(root.right)
        f(root)
        return res
    def kthSmallest2(self, root: TreeNode, k: int) -> int:
        stack = []
        cnt = 0
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            cnt += 1
            if cnt == k: return root.val
            root = root.right
